"""
题目：找到单链表的中间节点，如果有两个中间节点，则返回第二个中间节点。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def find_middle_node(head):
    # 初始化快慢指针，都指向头节点
    slow = head
    fast = head

    # 快指针每次走两步，慢指针每次走一步
    # 当快指针到达末尾时，慢指针正好在中间
    while fast and fast.next:
        slow = slow.next  # 慢指针前进一步
        fast = fast.next.next  # 快指针前进两步

    return slow  # 返回中间节点


# 辅助函数
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def get_node_value(node):
    return node.val if node else None  # 返回节点值，处理空节点情况


# 测试
head1 = create_linked_list([1, 2, 3, 4, 5])
print(get_node_value(find_middle_node(head1)))  # 输出: 3

head2 = create_linked_list([1, 2, 3, 4, 5, 6])
print(get_node_value(find_middle_node(head2)))  # 输出: 4（两个中间节点时返回第二个）
